    IOI. 7 (Urcarea unui munte) Un club de alpinisti are P(1P20) membri, 
numerotati de la 1 la P. Toti au aceeasi viteza de deplasare si vitezele la 
urcare si coborre coincid. Alpinistul i consuma C(i) unitati de resursa pe zi,
indiferent ct cara, si poate cara cel mult S(i) astfel de unitati.
Toate numerele sunt ntregi, citite de la tastatura. Fie N(1N100) numarul de 
zile n care dorim sa se ajunga n vrf. Muntele poate fi nsa foarte nalt 
astfel nct un singur alpinist nu poata sa ajunga n vrf si sa se ntoarca la 
baza cu resursele pe care le poate transporta. De aceea un grup de alpinisti 
va pleca din acelasi loc si n acelasi moment, cu scopul ca cel putin unul sa 
ajunga n vrf si toti sa aiba resurse suficiente pentru a se ntoarce la baza. 
Un alpinist care coboara nainte de a ajunge n vrf cedeaza celorlalti 
resursele suplimentare fata de cele necesare rentoarcerii sale la baza. 
Alpinistii nu se odihnesc pe parcursul drumului. Problema consta n a produce, 
daca exista, o planificare de urcare.
   Sa se scrie un program care sa realizeze urmatoarele:
 1) Citeste de la tastatura (conform sabloanelor din exemple) numarul N de zile 
n care trebuie sa se ajunga n vrf, numarul P de alpinisti si numerele C(i), 
S(i),1iP. Intrarile fara sens trebuiesc refuzate;
 2) Stabileste o planificare de urcare; determina un grup de alpinisti a(1),
a(2), ..,a(k) care sa participe la urcare si (pentru toti j,1jk) numarul M(j) 
de resurse cu care pleaca alpinistul a(j).
De remarcat ca nu pentru orice date de intrare exista o planificare de urcare;
 3) Afiseaza pe ecran:
- numarul k de alpinisti care participa la urcare;
- numarul total de resurse necesare;
- numerele de ordine a(1),a(2),..,a(k) ale alpinistilor participanti;
- pentru fiecare j=1,2,..,k numarul initial de resurse M(j) cu care pleaca 
alpinistul a(j);
- ziua D(j) cnd alpinistul a(j) ncepe coborrea;
              4) O planificare de urcare se numeste optima daca:
- numarul de alpinisti care participa este minim;
- dintre grupurile satisfacnd conditia precedenta este ales cel pentru care 
cantitatea totala de resurse consumata este minima.
   Se cere se determine o planificare aproape optima.
Exemplu: Un dialog posibil cu programul este:
Zile pentru a ajunge n vrf: 4
Numarul membrilor clubului: 5
Maximul de resurse pentru alpinistul 1: 7
Consumul zilnic al alpinistului 1: 1
Maximul de resurse pentru alpinistul 2: 8
Consumul zilnic al alpinistului 2: 2
Maximul de resurse pentru alpinistul 3: 12
Consumul zilnic al alpinistului 3: 2
Maximul de resurse pentru alpinistul 4: 15
Consumul zilnic al alpinistului 4: 3
Maximul de resurse pentru alpinistul 5: 7
Consumul zilnic al alpinistului 5: 1
2 alpinisti necesari; cantitatea totala de resurse este 10
Alpinistii 1,5 pleaca
Alpinistul 1 cara 7 si coboara dupa 8 zile
Alpinistul 5 cara 3 si coboara dupa 1 zi
Alte date (Y/N) Y
Zile pentru a ajunge n vrf: 2
Numarul membrilor clubului: 1
Maximul de resurse pentru alpinistul 1: 3
Consumul zilnic al alpinistului 1: 1
Urcare imposibila
Alte date (Y/N) N
Good bye
================================
Solutia 1  (Peter Szolt)

 Folosesc o metoada greedy, care da totdeauna solutie optima privind numarul
de alpinisti, dar nu e totdeauna optima numarul de resurse. Enuntul nu cere
o solutie optima, dar nici nu prcizeaza ca ce inseamna "aproape optima".

program IOI7;
uses crt;
const max=20;
var
  p,n,i,j,k:byte;
  c,s:array[1..max] of integer;
  r:array[1..max] of real;
  idx,cob:array[1..max] of byte;
  more,res:integer;
  alp:byte;
  ke:char;
begin
repeat
clrscr;
write('Zile pentru a ajunge la varf:');
readln(n);
write('Numarul membrelor clubului:');
readln(p);
for i:=1 to p do begin
  repeat
  write('Maximul de resurse pentru alpinistul ',i,':');
  readln(s[i]);
  write('Consumul zilnic al alpinistului ',i,':');
  readln(c[i]);
  if (c[i]<0) or (s[i]<c[i]) then begin
    writeln('Date invalide!');
  end;
  until not ((c[i]<0) or (s[i]<c[i]));
  r[i]:=s[i]/c[i];
  idx[i]:=i;
  cob[i]:=0;
end;
for i:=1 to p-1 do
  for j:=i+1 to p do begin
    if r[idx[i]]<r[idx[j]] then begin
      k:=idx[i];
      idx[i]:=idx[j];
      idx[j]:=k;
    end;
  end;
if n=0 then begin
  writeln('Nu sunt necesari nici alpinisti, nici resurse!');
end else begin
  alp:=1;
  i:=1;
  more:=2*n*c[idx[i]]-s[idx[i]];
  cob[idx[i]]:=n;
  res:=s[idx[i]];
  k:=2*n-trunc(s[idx[i]]/c[idx[i]]);
  while (alp<n) and (k<n) and (more>0) do begin
     inc(alp);
     inc(i);
     n:=k;
     more:=more+2*n*c[idx[i]]-s[idx[i]];
     k:=2*n-trunc(s[idx[i]]/c[idx[i]]);
     res:=res+s[idx[i]];
     cob[idx[i]]:=n;
  end;
  if (more>0) then writeln('Urcare imposibila!') else begin
    res:=res+more;
    s[idx[i]]:=s[idx[i]]+more;
    writeln(alp,' alpinisti necesari; cantitatea totala de resurse este ',res);
    for i:=1 to alp do begin
      writeln('Alpinistul ',idx[i],' cara ',s[idx[i]],' si coboara dupa ',cob[idx[i]],' zile');
    end;
  end;
end;
repeat
  write('Alte date (Y/N)');
  ke:=upcase(readkey);
until ke in['Y','N'];
until ke='N';

end.
---------------------------------
Solutia (Vlad Atanasiu)
Program:
uses crt;
label start;
type cerinte=record
             zile,resurse:integer;
             end;
     stiri=record
           nr_alpinist,unit_pe_zi,max_unit,putere:integer;
           end;
var club:array[1..20] of stiri;
    lista:array[1..20] of cerinte;
    necesar,ramas,distanta,curent,i,j,nr_membri,total,nr_alpinisti:byte;
    s:stiri;
    imposibil,gasit:boolean;
    c:char;

function cat_trebuie(necesar:cerinte;alpinist:integer):integer;
{ intoarce numarul de resurse necesare alpinistului alpinist ca sa
indeplineasca
  conditiile puse de necesar }
begin
cat_trebuie:=necesar.zile*club[alpinist].unit_pe_zi+necesar.resurse;
end;

function min(x,y:integer):integer;
begin
min:=x;
if y<x then min:=y;
end;

begin
clrscr;
start:
write('Zile pentru a ajunge in varf : ');
readln(distanta);
write('Numarul membrilor clubului : ');
readln(nr_membri);
for i:=1 to nr_membri do
    begin
    club[i].nr_alpinist:=i;
    write('Maximul de resurse pentru alpinistul ',i,' : ');
    readln(club[i].max_unit);
    write('Consumul zilnic al alpinistului ',i,' : ');
    readln(club[i].unit_pe_zi);
    club[i].putere:=club[i].max_unit div club[i].unit_pe_zi;
    end;
for i:=1 to nr_membri do
    for j:=nr_membri downto i+1 do
        if club[j].putere>club[j-1].putere then
           begin
           s:=club[j];
           club[j]:=club[j-1];
           club[j-1]:=s;
           end;
curent:=1;
imposibil:=false;
gasit:=false;
distanta:=4;
ramas:=0;
total:=0;
nr_alpinisti:=0;
repeat
      necesar:=ramas+distanta*club[curent].unit_pe_zi;
      { necesar reprezinta cantitatea de resurse disponibila care ramane dupa
urcare }
      if necesar>club[curent].max_unit then imposibil:=true
      else begin
           write('Alpinistul ',club[curent].nr_alpinist,' cara ');
           inc(nr_alpinisti);
           if
necesar<=club[curent].max_unit-distanta*2*club[curent].unit_pe_zi-ramas then
              begin
              write(distanta*2*club[curent].unit_pe_zi+ramas);
              total:=total+distanta*2*club[curent].unit_pe_zi+ramas;
              end
           else
              begin
              write(club[curent].max_unit);
              total:=total+club[curent].max_unit;
              end;
           writeln(' si coboara dupa ',distanta);
           distanta:=distanta*2-(club[curent].max_unit-ramas) div
club[curent].unit_pe_zi;
           ramas:=distanta div club[curent].unit_pe_zi;
           if distanta<=0 then gasit:=true;
           end;
      inc(curent);
until imposibil or gasit;
if not imposibil then writeln(nr_alpinisti,' necesari; cantitate totala
',total)
                 else writeln('Urcare imposibila');
writeln;
repeat
      write('Alte date (Y/N) ');
      readln(c);
      c:=upcase(c);
until c in ['Y','N'];
if c='Y' then goto start;
end.
------------------------------------------------------
